
\begin{frame}\frametitle{Problemstellung}
\includegraphics[height=4cm]{lmt_hole_candidateEdges.jpg}
\vspace{0.5cm}
\begin{enumerate}
\item Polygonlöcher im LMT-Skelett finden
\item Polygone optimal triangulieren
\end{enumerate}
\end{frame}

\begin{frame}\frametitle{Finden der Löcher}
\begin{itemize}
\item Nutzung der ``candidate edges`` zur Bestimmung involvierter Punkte
\item Problem: Punkte sind ungeordnet
\end{itemize}
\vspace{0.4cm}
\includegraphics[height=4cm]{lmt_hole.png}
\vspace{0.4cm}
\begin{itemize}
\item Kreissuche durch modifizierte DFS
\end{itemize}
\end{frame}

\begin{frame}\frametitle{Optimale Polygontriangulation}
\begin{itemize}
\item gegeben: Polygon $P=\{v_0, .. ,v_n\}$
\vspace{0.4cm}
\item Lösung mit dynamischer Programmierung in $O(n^3)$
\vspace{0.1cm}
\item Subproblem $t[i, j]$: optimale Triangulation rechts neben der Sehne zwischen $v_i$ und $v_j$\\
\vspace{0.1cm}
$t[i,j] = \begin{cases}
0 & \text{wenn } j = i+1\\
min_{i<k<j}(t[i,k] + t[k,j] + w(v_i,v_k,v_j)) & \text{wenn } j > i + 1
\end{cases}$
\vspace{0.1cm}
\item $t[0, n]$ ist optimale Triangulation des Polygons
\end{itemize}
\end{frame}